/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/word-ladder
   @Language: C++
   @Datetime: 16-02-09 08:51
   */

class Solution {
public:
	/*
	 * @param start: a string
	 * @param end: a string
	 * @param dict: a set of string
	 * @return: An integer
	 */
	int ladderLength(string &start, string &end, unordered_set<string> &dict) {
		// write your code here
		queue<string> q({start});
		for(int step=1; q.size(); ++step){
			for(int size=q.size(); size--; q.pop()){
				const string &word=q.front();
				for(int i=0; i<word.length(); ++i){
					string s=word;
					for(char ch='a'; ch<='z'; ++ch){
						if(word[i]==ch) continue;
						s[i]=ch;
						if(s==end) return step+1;
						if(dict.count(s)==0) continue;
						q.push(s);
						dict.erase(s);
					}
				}
			}
		}
		return 0;
	}
};
